/**
 * @param {number} n
 * @param {number} x
 * @return {number}
 */
var numberOfWays = function (n, x) {
  const MOD = 1e9 + 7;

  // 计算k的x次幂
  const power = (k) => {
    let result = 1;
    for (let i = 0; i < x; i++) {
      result *= k;
    }
    return result;
  };

  // 找出所有可能的k值，使得k^x <= n
  const powers = [];
  let k = 1;
  while (true) {
    const p = power(k);
    if (p > n) break;
    powers.push(p);
    k++;
  }

  // 使用动态规划
  // dp[i]表示组成数字i的方案数
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; // 初始状态：组成0有一种方法（不使用任何数字）

  for (const powerVal of powers) {
    // 从后往前更新，避免重复使用同一个底数
    for (let j = n; j >= powerVal; j--) {
      dp[j] = (dp[j] + dp[j - powerVal]) % MOD;
    }
  }

  return dp[n];
};
